package mother_merge;

/**
 * Created by xupeng20 on 2019/1/30.  归并算法模板
 */
public class Java_Mother_Merge {
    /**
     * 排序+合并过程 log(n).n
     */
    public static int[] mergeSort(int[] arr,int L ,int R){
        if (L==R || arr.length<2){
            return arr;
        }
        int[] sort = sort(arr, L, R);
        return sort;
    }
    public static int[] sort(int[] arr,int L,int R){
        //结束条件
        if (L>=R){
            return arr;
        }
        int mid = L+(R-L)/2;
        //左右排序
        sort(arr,L,mid);
        sort(arr,mid+1,R);
        //外部和排
        merge(arr,L,mid,R);
        return arr;
    }
    public static int [] merge(int[] arr,int L,int m,int R){
        //创建一个辅助数组
        int[] help = new int[R-L+1];
        //两数组正常合并,i辅助数组起点
        int i = 0;
        int p1 = L;
        int p2 = m+1;
        while (p1<=m && p2<=R){
            help[i++]= arr[p1]<arr[p2]?arr[p1++]:arr[p2++];
        }
        //一个数组越界
        while (p1 <= m){
            help[i++] =arr[p1++];
        }
        while (p2 <= R){
            help[i++] =arr[p2++];
        }
        //返回  新数组拷贝会原数组
        for (i=0;i<help.length;i++){
            arr[L+i] = help[i];
        }
        return arr;
    }
    public static void main(String[] args){
        int [] arr = {1,4,2,5,6,3};
        int[] mergeSort = mergeSort(arr, 0, arr.length-1);
        for (int temp:mergeSort){
            System.out.println(temp);
        }
    }
}
